/*************************************************************************
> File Name: greedy.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-13 14:53:22
> Description:
55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
************************************************************************/

// 思路：
// 数组f[i]记录位置i能否可达最大位置；
// 遍历数组，若该位置可跳跃更远，更新最大位置
// 若终点 则终点位1
#include <vector>
using namespace std;

class Solution
{
public:
    bool canJump(vector<int> &nums)
    {
        int length = nums.size();
        int jump = 0; // 可达最大位置
        if (length <= 1)
        {
            return true;
        }
        for (int i = 0; i < length; i++)
        {
            if (jump >= i)
            {
                if (nums[i] + i > jump)
                {
                    jump = nums[i] + i;
                    if (jump >= length - 1)
                    {
                        return true;
                    }
                }
            }
            else
            {
                return false;
            }
        }
        return false;
    }
};